package algorithm.difficult;

import java.awt.*;

public class UniquePathsIII980 {

    int count = 0;
    int temp = 0;
    int max = 0;

    public int uniquePathsIII(int[][] grid) {
        int x = 0, y = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    x = i;
                    y = j;
                } else if (grid[i][j] == 0) {
                    max++;
                }
            }
        }
        dfs(grid, x + 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x - 1, y);
        dfs(grid, x, y - 1);
        return count;
    }


    public void dfs(int[][] grid, int x, int y) {
        if (x >= grid.length || y >= grid[0].length || x < 0 || y < 0) {
            return;
        }
        if (grid[x][y] == 2 && temp == max) {
            count++;
            return;
        }
        if (grid[x][y] == -1 || grid[x][y] == 1) {
            return;
        }
        if (grid[x][y] == 0) {
            grid[x][y] = -1;
            temp++;
            //选择方向
            dfs(grid, x + 1, y);
            dfs(grid, x, y + 1);
            dfs(grid, x - 1, y);
            dfs(grid, x, y - 1);
            temp--;
            grid[x][y] = 0;
        }
    }

    public static void main(String[] args) {
        int i = new UniquePathsIII980().uniquePathsIII(new int[][]{{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 2, -1}});
        System.out.println(i);
    }
}
